# 最小覆盖子串： https://leetcode-cn.com/problems/minimum-window-substring/

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        """
            通过暴力的方式是，找到所有的子串（长度大于等于 t的），然后判断是否包含 t的所有字符，取最短的输出。
            问题装换为了两个： 
            1. 找到所有子串（长度大于等于 t的）
            2. 判断一个子串 是否包含 t的所有字符
        
            第一个问题： 很好解决， 我们以每一个字符的为开始，向后找长度大于 t的子串即可， 那么时间复杂度就是 O(n^2). 
            并且可以 先找到以每个字符开头，所有的子串，谁最小包括就停止，因为后面的串比符合且长度要长， 比如 ABCDEF ，找 ABC。  
            先以 A开头, 找到 ABC符合要求了，停止遍历， 没必要再找子串 ABCD， ABCDE了， 
            那么问题就转换为找到以每个字符开头 最小包含 t的子串， 因为最小子串一定是以某个字符开头的，所以一定在这些每个元素开头的最小子串之中！！  这个思路转换有点像这题： # 最大子序合(题目链接及动态规划讲解): https://www.zhihu.com/question/23995189
            第二个问题： 
            可以使用计数的方式，利用数组下标记录每个元素出现的次数， 与t中元素和元素出现的次数进行比较.

            后续编程中，发现，使用计数比较是否 子串出现 t ，利用上述做，会麻烦很多，但是稍微再想一下就是 滑动串口的解决方法（因为每个字符开始求最短符合子串， 可能会需要回溯 j指针~~~， 不如窗口方便，且效率高）。
        """
        n = len(s)
        # 1. 首先统计t中元素出现的次数 ord("z") - ord("A") = 57, 所以初始 58长度的数组
        charCountT = [0] * 58
        for c in t: charCountT[ord(c) - ord("A")] += 1
        # 2. 另外统计字符出现的个数, 例如 ABCA， 出现三个字符
        charT = 0
        for num in charCountT:
            if num > 0: charT += 1
        
        # 3. 找到每个字符开头，符合条件的最小子串
        charS = 0
        subSequenceSCount = [0] * 58
        # 记录符合条件子串的信息，长度， 左右下标
        rst = [-1, 0, 0]
        i = j = 0
        while j < n:
            """ 4. 先将当前元素添加进去，再做判断，也类似一个窗口[i, j]闭区间 """
            index = ord(s[j]) - ord("A")
            subSequenceSCount[index] += 1
            # 5. 如果同一元素，个数相同，那就说明有一位元素已经找到
            if subSequenceSCount[index] == charCountT[index]:
                charS += 1

            # 6. 当 charS == charT, 说明全部找到, 和rst比较谁小，保留谁
            while charS == charT:
                if rst[0] == -1 or rst[0] > j - i + 1:
                    rst[0] = j - i + 1
                    rst[1] = i
                    rst[2] = j
                
                index = ord(s[i]) - ord("A")
                subSequenceSCount[index] -= 1
                # 数量减1后，如果不够了，那减去一个匹配的字符
                if subSequenceSCount[index] < charCountT[index]:
                    charS -= 1
                i += 1

            j += 1
    
        return s[rst[1]: rst[2]+1] if rst[0] != -1 else ""


